package org.hw.algorithm.number;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm
 * @description:
 * @author: hewei
 * @date: 2023-05-30 14:06
 **/
public class NumberFactory {
    public static void main(String[] args) {

        System.out.println(fibonacci(6));
    }


    /**
     * 斐波那契数列(后一个数是前两个数之和): 0,1,1,2,3,5,8...
     *
     * */
    public static int fibonacci(int n) {
        if (n <=0) return 0;
        if (n == 1 || n == 2) return 1;
        return fibonacci(n-1) + fibonacci(n -2);
    }

    /**
     * 判断是否是偶数
     * 偶数的二进制最后一位一定是0，与 1 进行 & 运算结果一定为0
     * 例如：
     *      4   110  |  5   111
     * &             |
     *      1   001  |  1   001
     * =             |
     *      0   000  |  1   001
     * */
    public static boolean isEven(int n) {
        return (n&1)==0;
    }

    /**
     * 一个有序的二维数组table：
     * 行：从左到有升序
     * 列：从上到下升序 
     * 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增， 
     * 因此从左下角开始查找，当要查找数字比左下角数字大时。右移 要查找数字比左下角数字小时，上移。这样找的速度最快
     *
     * */
    public static boolean searchTable(int[][] table, int target){
        /*行*/
        int row= table.length;
        /*列*/
        int column = 0;
        while (row >= 0 && column < table[0].length){
            if (target == table[row][column]) return true;
            if ( target < table[row][column]) row--;
            if (target > table[row][column]) column++;
        }
        return false;
    }

    /**
     * 计算a的n次方(a^n)
     * 利用中间计算结果，例如a的4次方，如果计算a的2次方结果为tmp，
     * 那么a的4次方的结果就是tmp乘tmp，a的5次方就是tmp*tmp*a
     * 偶数：a^4=a^2*a^2
     * 基数：a^5=a^2*a^2*a
     * */
    public static double power(double a, int n) {
        if (0==n) return 1;
        if (1==n) return a;
        /*计算a的n/2次方*/
        double t=power(a,Math.abs(n/2));
        if (n>0){
            /* n是偶数，结果为tmp*tmp，奇数：tmp*tmp*a */
            return Math.abs(n % 2) == 0 ? t*t : t*t*a;
        }else {
            /*如果n是负数，则返回结果的倒数（递归方法中最外层保留n的初始符号位）*/
            return Math.abs(n % 2) == 0 ? 1 / (t*t) : 1 / (t*t*a);
        }
    }
    /*用位运算进行加法计算*/
    public static int numberAdd(int a,int b){
        int sum=0;
        int cary=0;
        do{
            /*未进位的和*/
            sum=a^b;
            /*进位值*/
            cary=(a&b)<<1;
            a=sum;
            b=cary;
        }while (cary!=0);
        return sum;
    }

    /**
     * 最大子数组的和
     * Kadane算法步骤
     * 初始化两个变量：
     * max_current：当前子数组的最大和，初始值为数组的第一个元素。
     * max_global：全局最大子数组的和，初始值也为数组的第一个元素。
     * 遍历数组中的每一个元素（从第二个元素开始）：
     * 更新max_current为当前元素和max_current + 当前元素中的较大值。
     * 更新max_global为max_global和max_current中的较大值。
     * 遍历结束后，max_global即为所求的最大子数组的和。
     * */
    public static int maxSubArr(int[] arr) {
        if (arr==null || arr.length==0) return 0;
        int maxCurr=arr[0];
        int maxTotal=arr[0];
        for (int i = 1; i < arr.length; i++) {
            // 当前子数组的最大和
            maxCurr = Math.max(arr[i], arr[i] + maxCurr);
            // 全局最大和
            maxTotal=Math.max(maxCurr,maxTotal);
        }
        return maxTotal;
    }

    /**
     * 找出一个数组中和为特定值的两个数，返回两个数的下标，没有找到返回空数组
     */

    public static int[] twoSum(int[] arr, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int diff=target-arr[i];
            if (map.containsKey(diff)) {
                return new int[]{map.get(diff), i};
            }
            map.put(arr[i],i);
        }
        return new int[]{};
    }
    /**
     * 获取一个数的最高位的值
     * */
    public static int getHighestDigit(int number) {
        // 将整数转换为字符串
        String numberStr = Integer.toString(number);
        // 获取字符串的第一个字符
        char firstChar = numberStr.charAt(0);
        // 将字符转换回整数
        int highestDigit = Character.getNumericValue(firstChar);
        return highestDigit;
    }
}
